package com.algorithm.dijkstra;

public class Graph {
    private char[] vertexs;
    private int[][] matrix;
    private VistiedVertex vv;

    public Graph(char[] vertexs,int[][] matrix){
        this.vertexs = vertexs;
        this.matrix = matrix;
    }
    public void showGraph(){
        for (int[] link:matrix){
            for (int k:link){
                System.out.format("%6d",k);
            }
            System.out.println();
        }
    }

    public void dijkstra(int index){
        vv = new VistiedVertex(vertexs.length,index);
        //更新index顶点到邻接结点的距离和前驱结点
        update(index);
        for(int i = 0;i<vertexs.length;i++){
            index = vv.updateArr();
            update(index);
        }
    }
    /**
     * 更新index下标顶点到周围顶点的距离和周围顶点的前驱顶点
     */
    public void update(int index){
        int len = 0;
        for(int i = 0;i<matrix[index].length;i++){
            //出发顶点到index顶点的距离 + index与邻接结点的距离
            len = vv.getDis(index) + matrix[index][i];
            //如果该顶点未被访问，且距离小于出发顶点到顶点i的距离，则进行更新
            if(!vv.already_arr[i] && len <vv.getDis(i)){
                //更新该顶点到邻接结点的距离，并见邻接结点的前驱结点设置为该结点
                vv.updatePre(i,index);
                vv.updateDis(i,len);
            }
        }
    }

    public void showResult(){
        vv.show();
    }

}
